package com.algorithm.liyc.echa;

import com.algorithm.liyc.entity.TreeNode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 0106.从中序与后序遍历序列构造二叉树
 * 根据一棵树的中序遍历与后序遍历构造二叉树。
 * 注意:
 * 你可以假设树中没有重复的元素。
 *
 * 首先回忆一下如何根据两个顺序构造一个唯一的二叉树，相信理论知识大家应该都清楚，就是以 后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。
 * 如果让我们肉眼看两个序列，画一棵二叉树的话，应该分分钟都可以画出来。
 *
 * 来看一下一共分几步：
 * ●  第一步：如果数组大小为零的话，说明是空节点了。
 * ●  第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
 * ●  第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
 * ●  第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
 * ●  第五步：切割后序数组，切成后序左数组和后序右数组
 * ●  第六步：递归处理左区间和右区间
 * @author Liyc
 * @date 2024/1/9 15:35
 **/

public class Solution14 {
    Map<Integer, Integer> map;  // 方便根据数值查找位置

    /**
     * 106.从中序与后序遍历序列构造二叉树
     * @param inorder
     * @param postorder
     * @return
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {// 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }
        return findNode(inorder, 0, inorder.length, postorder, 0, postorder.length);//前闭后开
    }

    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        // 参数里的范围都是前闭后开
        if (inBegin >= inEnd || postBegin >= postEnd) {// 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        int rootOfIndex = map.get(postorder[inorder.length - 1]);// 找到后序遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootOfIndex]);// 构造结点
        int lenOfIndex = rootOfIndex - inBegin;// 保存中序左子树个数，用来确定后序数列的个数
        root.left = findNode(inorder, inBegin, rootOfIndex, postorder, postBegin, postBegin + lenOfIndex);
        root.right = findNode(inorder, rootOfIndex + 1, inEnd, postorder, postBegin + lenOfIndex, postEnd - 1);
        return root;
    }

    /**
     * 105.从前序与中序遍历序列构造二叉树
     * @param inorder
     * @param preorder
     * @return
     */
    public TreeNode buildTree2(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {// 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }
        return findNode(inorder, 0, inorder.length, preorder, 0, preorder.length);//前闭后开
    }

    public TreeNode findNode2(int[] preorder, int postBegin, int postEnd, int[] inorder, int inBegin, int inEnd) {
        // 参数里的范围都是前闭后开
        if (inBegin >= inEnd || postBegin >= postEnd) {// 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        int rootOfIndex = map.get(preorder[inBegin]);// 找到前序遍历的第一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootOfIndex]);// 构造结点
        int lenOfIndex = rootOfIndex - inBegin;// 保存中序左子树个数，用来确定前序数列的个数
        root.left = findNode(preorder, postBegin + 1, postBegin + lenOfIndex + 1, inorder, inBegin, rootOfIndex);
        root.right = findNode(preorder, postBegin + lenOfIndex + 1, postEnd, inorder, rootOfIndex + 1, inEnd);
        return root;
    }
}
